package leetcode每日一题;


/**
 * 1. 问题描述
 *      将整数进行反转，但是有一个要求；
 *          假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。
 *          请根据这个假设，如果反转后整数溢出那么就返回 0。
 *
 * 2. 算法分析
 *      此题的算法思路非常简单，但是值得注意的是我们如何判断是否溢出
 *      举个具体的例子：
 *          x = 123    ans = 0
 *          1. x % 10 = 3    ans = 300   x = x / 10 = 12
 *          2. x % 10 = 2    ans = 10 * 1 * 2
 *          321 = 300 + 20 + 1 = 3 * 10*10 + 2 * 10 + 1
 *                             = 10 * (3 * 10 + 2) + 1
 *
 *          上述过程可以通过栈来实现，但是我们也可以不通过栈
 *          pop = x % 10 弹出x的当前最低位
 *          x = x / 10  更新x
 *
 *          rev = 0
 *          temp = rev * 10 + pop
 *          rev = temp
 *     在计算temp的过程中就会发生溢出，所以我们需要判断temp在什么条件下会溢出
 *     注意到2^31-1的个位上数字位7，-2^31的个位上位8   (利用周期性容易计算出来)
 *
 *     如果当前x为正整数 rev > 0,此时
 *          temp = rev * 10 + pop
 *     如果temp溢出
 *          temp > 2^31-1
 *          rev * 10 + pop > 2^31-1
 *     此时有两种情况：
 *          1. rev > INTMAX / 10  此时一定溢出
 *          2. rev == INTMAX  只要pop > 7 ，此时一定溢出
 *     如果x为负的情况分析同上
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 整数反转 {
    public static void main(String[] args) {
        System.out.println(reverse(-123));
    }

    public static int reverse(int x) {
        int rev = 0;
        int pop = 0;
        while (x != 0) {
            pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) {
                return 0;
            }
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) {
                return 0;
            }
            rev = rev * 10 + pop; // 注意rev的更新不能放在判断之前 rev从0开始，判断当前的rev，如果先修改在判断，那么修改之后的值可能直接溢出，
            // 但是为修改之前可能还没有溢出
        }
        return rev;
    }
}
